package com.xiayuanxing.arithmetic.DataStructures.Search;

import java.util.ArrayList;

/**
 * @program: arithmetic
 * @description: 二分查找法
 * @author: xia yuan xing
 * @create: 2021-09-27 16:08
 */
public class BinarySearch {




    public static void main(String[] args) {

        /**
         * 原始数组：注意二分查找的前提是该数组是有序的
         */
        int[] arr = {0, 1, 2, 3, 4, 4, 4, 4, 7, 8, 9};

//        int index = binarySearch(arr, 0, 8, 9);
        ArrayList<Integer> integers = binarySearch1(arr, 0, arr.length - 1, 4);

        System.out.println("查找的值下标为："+integers);
    }


    /**
     * 二分查找法(获取单个下标)
     * @param array 原始数组
     * @param left 左边的下标
     * @param right 右边的下标
     * @param findValue 要查找的值
     * @return 返回该值的下标
     */
    public static int binarySearch(int[] array,int left,int right,int findValue){

        if (left > right){
            //说明递归整个数组没有找到该数据
            return -1;
        }
        //获取中轴值的下标
        int mid = (left + right)/2;
        //获取中轴值
        int midValue = array[mid];

        if (findValue > midValue){
            //向右递归
            return binarySearch(array,mid + 1,right,findValue);
        }else if (findValue < midValue){
            //向左递归
            return binarySearch(array,left,mid - 1,findValue);
        }else {
            return mid;
        }

    }


    /**
     * 二分查找法(获取多个下标)
     * @param array 原始数组
     * @param left 左边的下标
     * @param right 右边的下标
     * @param findValue 要查找的值
     * @return 返回该值的下标
     * 思路：
     * 1.在找到mid值时，先不返回
     * 2.向mid索引值的左边扫描，将所有满足查找值的下标加入到一个集合中
     * 3.向mid索引值的右边扫描，将所有满足查找值的下标也加入到一个集合中
     * 4.将集合返回
     */
    public static ArrayList<Integer> binarySearch1(int[] array, int left, int right, int findValue){

        if (left > right){
            //说明递归整个数组没有找到该数据
            return new ArrayList<Integer>();
        }
        //获取中轴值的下标
        int mid = (left + right)/2;
        //获取中轴值
        int midValue = array[mid];

        if (findValue > midValue){
            //向右递归
            return binarySearch1(array,mid + 1,right,findValue);
        }else if (findValue < midValue){
            //向左递归
            return binarySearch1(array,left,mid - 1,findValue);
        }else {
            ArrayList<Integer> resultIndexList = new ArrayList<>();
            //向左扫描
            int temp = mid -1;
            while (true){
                if (temp < 0 || array[temp] != findValue){
                    break;
                }
                resultIndexList.add(temp);
                temp -= 1;
            }
            resultIndexList.add(mid);

            //向右扫描

          temp = mid + 1;
            while (true){
                if (temp > array.length - 1 || array[temp] != findValue){
                    break;
                }
                resultIndexList.add(temp);
                temp += 1;
            }
            return resultIndexList;
        }

    }

}